package allCellsDistOrder;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {
    class Node{
        int x;
        int y;

        int dis;
        public Node(int x,int y,int dis){
            this.x=x;
            this.y=y;
            this.dis=dis;
        }
    }
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int [][]arr=new int[rows*cols][2];
        List<Node> nodes=new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                Node n=new Node(i,j,Math.abs(i-rCenter)+Math.abs(j-cCenter));
                nodes.add(n);
            }
        }
        nodes.sort(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.dis-o2.dis;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            arr[i][0]=nodes.get(i).x;
            arr[i][1]=nodes.get(i).y;
        }
        return arr;
    }
}
//桶排序
//class Solution {
//    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
//        int maxDist = Math.max(rCenter, rows - 1 - rCenter) + Math.max(cCenter, cols - 1 - cCenter);
//        List<List<int[]>> bucket = new ArrayList<List<int[]>>();
//        for (int i = 0; i <= maxDist; i++) {
//            bucket.add(new ArrayList<int[]>());
//        }
//
//        for (int i = 0; i < rows; i++) {
//            for (int j = 0; j < cols; j++) {
//                int d = dist(i, j, rCenter, cCenter);
//                bucket.get(d).add(new int[]{i, j});
//            }
//        }
//        int[][] ret = new int[rows * cols][];
//        int index = 0;
//        for (int i = 0; i <= maxDist; i++) {
//            for (int[] it : bucket.get(i)) {
//                ret[index++] = it;
//            }
//        }
//        return ret;
//    }
//
//    public int dist(int r1, int c1, int r2, int c2) {
//        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
//    }
//}
